﻿#define _CRT_SECURE_NO_WARNINGS

#include"sort.h"
#include "stack.h"

//交换
void Swap(HPDataType* x, HPDataType* y)
{
	HPDataType tmp = *x;
	*x = *y;
	*y = tmp;
}
//向下调整算法    // 时间复杂度：O(logn)      //在向下调整算法里，无论堆中有多少个节点，在最坏情况下，算法最多只需要从根节点一直走到叶子节点。也就是说，算法执行的操作次数取决于从根节点到叶子节点的最长路径长度，而这个最长路径长度就是树的高度。
void AdjustDown(HPDataType* arr, int parent, int n)     //从父亲找孩子，此时堆是完全二叉树，存在左子树，与右子树，即有左孩子与右孩子，因此要根据是需要调整成大堆，还是小堆，来选择是要交换较大的孩子，还是较小的孩子。注意：无论是大堆还是小堆，当孩子等于父亲时也是满足大堆或小堆的。
{
	assert(arr);
	int child = parent * 2 + 1;    //左孩子   //注意：从父亲找孩子，是存在找到左子树，和找到右子树的    
	while (child < n)    //不能将child + 1 < n 放在此处判断，会导致：如果是最后底层的右孩子是size 的前一个数据，那么就直接跳出了，不会判断要不要发生Swap
	{
		//大堆：<
		//小堆：>
		if (child + 1 < n && arr[child] > arr[child + 1])    //此时child + 1 就是右孩子   //child + 1 < n  是为了保证child++ 后不会越界，也可以理解为先保证有右孩子，再去比较这两个孩子
		{
			child++;    //此时的孩子就是较大的
		}
		//大堆：<
		//小堆：>
		if (arr[parent] > arr[child])
		{
			Swap(&arr[parent], &arr[child]);
			parent = child;            // 此处往下继续调整child 与parent 是建立在发生了Swap 的前提下的，当没有Swap 的时候，是直接跳出while循环
			child = parent * 2 + 1;
		}
		else {
			break;
		}
	}
}
//
//时间复杂度为：n*log(n)
//实际的堆排序写法，直接利用堆的存储结构数组即可
void HeapSort(int* arr, int n)       //没有去新创建堆，而是直接通过AdjustUp、AdjustDown函数，来调整数组，实现堆排序（因为堆的存储结构就是数组嘛，逻辑结构才是我们说的完全二叉树）
{
	assert(arr);
	//向下调整算法建堆             //从最后一个child 的parent 开始，i--，开始遍历，依次调用向下调整算法
	//时间复杂度：On         //因为从上往下，要往下走的节点个数越少，即要挪动层次大的节点数少
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(arr, i, n);
	}
	//向上调整算法建堆               //i从0开始，i++，将每新加入进来的数据都向上调整，而AdjustUp 函数会始终维护为堆
	//时间复杂度：O(n * log(n))         //因为从下往上走，要往走且走的层次多的节点数多，因此更复杂
	/*for (int i = 0; i < n; i++)
	{
		AdjustUp(arr, i);
	}*/
	while (n > 0)
	{
		Swap(&arr[0], &arr[n-- - 1]);     //先将堆顶的最值与size-1 处的数据交换，再size--，再调整堆，如此循环即可完成直接对数组的堆排序
		AdjustDown(arr, 0, n);    //此处使用向下调整算法是因为，交换数据再调整为堆
	}
}

//冒泡排序
//时间复杂度O（n^2)               //由于log(n) < n 所以堆排序的时间复杂度要优于冒泡排序
//最好O(1)
void BubbleSort(int* arr, int n)
{
	assert(arr);
	for (int i = 0; i < n - 1; i++)
	{
		int flag = 0;
		for (int j = 0; j < n - i - 1; j++)
		{
			if (arr[j] < arr[j + 1])
			{
				Swap(&arr[j], &arr[j + 1]);
				flag = 1;
			}
		}
		if (!flag)
		{
			break;
		}
	}
}


//直接插入排序
//分两个区域，前面为已排序区，后面为待排序的。所谓插入即每次将重待排序区的数据，直接插入到已排序区的正确位置处
void InsertSort(int* arr, int n)   
{
	//assert(arr);
	//for (int i = 0; i < n - 1; i++)            //我写的直接插入排序
	//{
	//	int end = i;
	//	int tmp = arr[i + 1];    //注意：此处不将tmp 设为下边，而是直接设为一个变量是为了可以做到保存end+1 下标处的数据

	//	if (arr[end] > tmp)
	//	{
	//		int flag = 0;
	//		while (end >= 0)
	//		{
	//			arr[end + 1] = arr[end];
	//			if (arr[end] < tmp)
	//			{
	//				flag = 1;
	//				arr[end + 1] = tmp;
	//				break;
	//			}
	//			end--;
	//		}
	//		if (flag == 0)
	//		{
	//			arr[0] = tmp;
	//		}
	//	}
	//	else {
	//		continue;
	//	}
	//}



	                                                //绵姐写的
	for (int i = 0; i < n - 1; i++)                 //尽管实现细节不同，但代码逻辑，两段代码的时间复杂度完全相同。
	{                                                //绵姐的要更简洁，优于我的
		int end = i;
		int tmp = arr[end + 1];
		while (end >= 0)
		{
			if (arr[end] > tmp)
			{
				arr[end + 1] = arr[end];
				end--;
			}
			else {
				break;
			}
		}
		arr[end + 1] = tmp;
	}
	
}


//希尔排序
//时间复杂度：在一般情况下可视为O(n^1.3)，具体无法计算出
//且最开始为n，再升高，最后再趋向与n，最高处即为时间复杂度，还没有理论可以计算出
void ShellSort(int* arr, int n)
{
	assert(arr);
	int gap = n;
	while (gap > 1)
	{
		gap = gap / 3 + 1;    //对于偶数和奇数都是可以的
		//gap = gap / 2;   //对于奇数是可以使得gap = 1 的，而对于偶数则会最后进入2 的死循环
		//这两个都是可以的，分组情况一般只是影响希尔排序的内部的效率，比如：
		//gap = gap / 3 + 1;
		//gap = gap / 3 + 1;     //但不会影响最后的计算结果，会影响效率

		for (int i = 0; i + gap < n; i++)     //由于最后一个下标为n-1，因此要保证end 对应的tmp的下标，要小于n，即刚好达到n-1
		{                             //设计成i++，是因为进一步的理解，将每次按相隔gap 的元素分组的i += gap ，改成i++，就是因为反正相隔gap 的元素都是要直接插入排序的，那么我们就没必要去刻意的控制i 每次的增量为gap，直接i++ 即可
			int end = i;
			int tmp = arr[end + gap];
				while (end >= 0)         
				{
					if (arr[end] > tmp)
					{
						arr[end + gap] = arr[end];
						end -= gap;
					}
					else {
						break;
					}
				}
				arr[end + gap] = tmp;    //统一处理
		}
	}
	
}




//直接选择排序
//时间复杂度：On2
void SelectSort(int* arr, int n)
{
	assert(arr);
	int begin = 0, end = n - 1;
	while (begin <= end)
	{
		int maxi = begin, mini = begin;
		for (int i = begin + 1; i <= end; i++)
		{
			if (arr[i] < arr[mini])
			{
				mini = i;      //每次都在begin 与end 之间找出min 值，与max 值，最后分别放在begin 以及end 处
			}
			if (arr[i] > arr[maxi])
			{
				maxi = i; 
			}
		}
		//此时maxi 与mini 都已分别指向最大，及最小的位置处
		//为了解决下面的问题，我们需要加个if 进行拦截
		if (mini == end)
		{
			mini = maxi;   //当mini 与end 重合的时候，因为当第一个Swap 交换后，maxi的位置才是mini 真正所需要待的位置，因此可以提前将mini 设置为maxi 所在的位置
		}
		Swap(&arr[maxi], &arr[end]);    
		Swap(&arr[mini], &arr[begin]);   //如果直接交换的话，那么此时如果mini 的下标与end 的下标重合的话，那么此时再去取mini 处的值的话，那么此时就已经不再是最小值了，真正的最小值已经来到了，刚刚maxi 的位置了
		
		begin++;
		end--;
	}
}

//找基准值函数
//Hoare 分区法，由快速排序的发明者 Tony Hoare 提出，是最原始的分区策略。
//int _QuickSort(int* arr, int left, int right)
//{
//	assert(arr);
//	int keyi = left;                   //我的
//	left++;
//	while (left < right)    //此处我的测试结果发现left < right 没有问题，不过绵姐写的是left <= right
//	{
//		while (left <= right && arr[left] < arr[keyi])    //注意要加上防left 超过right 的条件
//		{
//			left++;
//		}
//		while (left < right && arr[right] > arr[keyi])
//		{
//			right--;
//		}
//		if (left < right)  //此处我的测试结果发现left < right 没有问题，不过绵姐写的是left <= right
//		{
//			Swap(&arr[left++], &arr[right--]);
//		}
//	}
//	Swap(&arr[right], &arr[keyi]);
//	return right;
//}
int _QuickSort(int* arr, int left, int right)                
{
	int keyi = left;
	++left;                                                          //绵姐的
	while (left <= right)
	{
		//right:从右往左找比基准值要小的数据
		while (left <= right && arr[right] > arr[keyi])
		{
			--right;
		}
		//left:从左往右找比基准值要大的数据
		while (left <= right && arr[left] < arr[keyi])
		{
			++left;
		}
		//left和right交换
		if (left <= right)
		{
			Swap(&arr[left++], &arr[right--]);
		}
	}
	Swap(&arr[keyi], &arr[right]);
	return right;
}

//扩展：找基准值分区的方法还有：挖坑法，双指针法
//其中挖坑法了解即可，以下是双指针法：
int _QuickSort02(int* arr, int left,int right)
{
	assert(arr);
	int src, dst, keyi;
	//src = left + 1;  //都可以
	src = dst = keyi = left;
	while (src <= right)
	{
		if (arr[src] < arr[keyi] && ++dst != src)   //注意：此处if 条件判断&& 前后语句不能调整，因为发生交换的首要因素就是src 处的值要小于基准值，再如果满足此条件的情况下去判断，src 与dst 之间的距离，如果是连着的，那么也就不需要交换了，且此处只要满足&& 前面的条件，就一定会遇到++src，那么src就已经完成不管是要交换执行Swap 还是连着不交换不执行Swap 函数，此处的dst 都完成++了。
		{
			Swap(&arr[src], &arr[dst]);
		}
		src++;
	}
	Swap(&arr[dst], &arr[keyi]);
	return dst;
}

//快速排序
//当快速排序，面对有序数组时，时间复杂度会较高，趋近于O(n2)，而如果是正常情况下，一般其找基准值的函数逻辑结构类似于二叉树，为O(logn)，那么整体就是O(nlogn)
void QuickSort(int* arr, int left, int right)
{
	if (left >= right)
	{
		return;
	}
	//找好基准值
	int keyi = _QuickSort(arr, left, right);
	//int keyi = _QuickSort02(arr, left, right);

	QuickSort(arr, left, keyi - 1);
	QuickSort(arr, keyi + 1, right);
}


//迭代----借助堆
void QuickSortNonR(int* arr, int left, int right)
{
	assert(arr);
	if (left > right)  return;
	ST st;
	STInit(&st);
	int keyi = left;

	STPush(&st, right);
	STPush(&st, left);

	int tmp01 = 0;
	int tmp02 = 0;
	while (!STEmpty(&st))
	{
		left = STTop(&st);
		tmp01 = left;
		STPop(&st);

		right = STTop(&st);
		tmp02 = right;
		STPop(&st);

		keyi = left;
		left++;

		while (left <= right)
		{
			while (left <= right && arr[left] < arr[keyi])
			{
				left++;
			}
			while (left <= right && arr[right] > arr[keyi])
			{
				right--;
			}
			if (left <= right)
			{
				Swap(&arr[right--], &arr[left++]);
			}
			
		}
		Swap(&arr[right], &arr[keyi]);
		keyi = right;
		right = tmp02;
		left = tmp01;

		if (keyi - 1 > left)
		{
			STPush(&st, keyi - 1);
			STPush(&st, left);
		}
		if (keyi + 1 < right)
		{
			STPush(&st, right); 
			STPush(&st, keyi + 1); 
		}
		
	}
	STDesTory(&st);
}
//void QuickSortNonR(int* arr, int left, int right)           //绵姐的
//{
//	ST st;
//	STInit(&st);
//	StackPush(&st, right);
//	StackPush(&st, left);
//	while (!StackEmpty(&st))
//	{
//		//取栈顶两次
//		int begin = StackTop(&st);
//		StackPop(&st);
//
//		int end = StackTop(&st);
//		StackPop(&st);
//		//[begin,end]---找基准值
//		int keyi = begin;
//		int prev = begin, cur = prev + 1;
//		while (cur <= end)
//		{
//			if (arr[cur] < arr[keyi] && ++prev != cur)
//			{
//				Swap(&arr[prev], &arr[cur]);
//			}
//			cur++;
//		}
//		Swap(&arr[prev], &arr[keyi]);
//		keyi = prev;
//		//begin keyi end
//		//左序列[begin,keyi-1]   右序列[keyi+1,end]
//		if (keyi + 1 < end)
//		{
//			StackPush(&st, end);
//			StackPush(&st, keyi + 1);
//		}
//		if (begin < keyi - 1)
//		{
//			StackPush(&st, keyi - 1);
//			StackPush(&st, begin);
//		}
//	}
//	STDestroy(&st);
//}




//归并排序的递归部分   （归并排序，有递归，也有迭代）
void _MergeSort(int* arr, int left, int right, int* tmp)         //计算时间复杂度：单次复杂度 * 递归次数 =  n * logn （单次复杂度在下边已有表明，而由于拆分递归的过程，与二叉树相似，二分法，为logn）
{
	if (left >= right)
	{
		return;          //此时已不满足继续拆的条件了        //当left == right 的时候，已经只剩1 个元素了，为有序
	}

	int mid = (left + right) / 2;
	_MergeSort(arr, left, mid, tmp);
	_MergeSort(arr, mid + 1, right, tmp);

	//此时一个_MergeSort函数下的两组都已经拆成有序，开始合并排序
	int begin1 = left, end1 = mid;
	int begin2 = mid + 1, end2 = right;

	int index = begin1; //index 用于在tmp 中插入当前两组合并中，排好的数据     //此处没有将index 设置为0 ，也是因为比较 合并 排序的开始位置并总是都是从0 下标开始的
	while (begin1 <= end1 && begin2 <= end2 )    //保证数据的有效性
	{                                                                                              // n
		if (arr[begin1] < arr[begin2])
		{
			tmp[index++] = arr[begin1++];   //小的往前排，排升序时
		}
		else {
			tmp[index++] = arr[begin2++];
		}
	}
	
	//考虑两组中剩下的那一组数据的剩下部分，都直接排进tmp 中，因为两组各自组中，都是有序的
	while (begin1 <= end1)
	{
		tmp[index++] = arr[begin1++];
	}
	while (begin2 <= end2)     //不再需要多写if ，直接利用while 的循环判断即可
	{
		tmp[index++] = arr[begin2++];
	}

	//此时两两组都完成了排序之后，将tmp 中的值在一轮轮的递归中，都将排好序的部分赋给原数组arr
	for (int i = left; i <= right; i++)    //begin 等改变了，但是当前递归下的left right 并没有               n
	{
		arr[i] = tmp[i];
	}
}

//四 归并排序：        
//先将所有拆散，拆成都是有序的，一般就是拆成1 个1 个的，再合并，且在合并中排好序  //注意在合并排序时，是直接在tmp 中对应下标处去映射 排好
void MergeSort(int* arr, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);    //开辟出与原数组arr 同样大小的空间，排好序后再赋给原数组     //同时使用tmp 数组，也是为了保证合并 排序的时候，不会因为改变原数组arr 中的数据，从而影响比较后的排序
	_MergeSort(arr, 0, n - 1, tmp);    //常见递归写法
	free(tmp);

	tmp = NULL;  //加上更严谨
}




//非比较排序： 计数排序
void CountSort(int* arr, int n) 
{

}